/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
#ifndef _XTREE_H_VERSION_KL__
#define _XTREE_H_VERSION_KL__

#include "btree.h"

KL_BEGIN
template<typename Key, typename Type>
struct xtree_pair : public KL::pair<const Key, Type>
{
	typedef KL::pair<const Key, Type> _base;
	xtree_pair()
	{
	}
	explicit xtree_pair(typename _base::first_type const & key)
		: _base(key, typename _base::second_type())
	{
	}
	xtree_pair(typename _base::first_type const & key, typename _base::second_type const &value)
		: _base(key, value)
	{
	}
	xtree_pair(_base const &o)
		: _base(o)
	{
	}
	xtree_pair(KL::pair<Key, Type> const &o)
		: _base(o)
	{
	}
	bool operator == (typename _base::first_type const & key)
	{
		return _base::first == key;
	}
};
template<typename Pair, typename KeyCompare>
struct xtree_pair_compare 
	: public binary_function<Pair, typename Pair::first_type, bool>
{
protected:
	KeyCompare _func;
public:
	typedef binary_function<Pair, typename Pair::first_type, bool> _base;
	typedef Pair first_argument_type;
	typedef typename Pair::first_type second_argument_type;
	typedef bool result_type;
	
	bool operator ()(Pair const & left, second_argument_type const & key) const
	{
		return _func(left.first, key);
	}	
	bool operator ()(second_argument_type const & key, Pair const & right) const
	{	// not standard
		return _func(key, right.first);
	}
	bool operator ()(second_argument_type const & left,
		second_argument_type const & right) const
	{	// not standard
		return _func(_base::first, right);
	}
	bool operator ()(Pair const &left, Pair const &right) const
	{	// not standard
		return _func(left.first, right.first);
	}
};
template<typename Key, typename Type, typename KeyLess = KL::less<Key>, 
typename Allocate = KL::allocator<Type>, bool Mult = false>
class xtree 
	: public KL::btree<KL::xtree_pair<Key, Type>, 
	xtree_pair_compare<KL::xtree_pair<Key, Type>, KeyLess>,
	Allocate, Mult>
{
	// TYPE {
private:	
	typedef KL::btree<KL::xtree_pair<Key, Type>, 
		xtree_pair_compare<KL::xtree_pair<Key, Type>, KeyLess>,
		Allocate, Mult> _base;
public:
	typedef Key key_type;
	typedef Type mapped_type;
	typedef KL::xtree_pair<key_type, mapped_type> pair;
	typedef KL::pair<typename _base::const_iterator, typename _base::const_iterator> range_pair;
	// TYPE }
public:
	// CONSTRUCT {
	xtree()
	{
	}
	xtree(xtree const &o)
		: _base(o)
	{
	}
	xtree & operator = (xtree const &o)
	{
		if(&o == this) return *this;
		*(_base*)this = (_base)o;
		return *this;
	}
	// CONSTRUCT }
	// INSERT {
	KL::pair<typename _base::iterator, bool> insert(pair const &value)
	{
		bool flag;
		typename _base::_node_pointer node = _base::_insert(value.first, flag);
		_base::_visit(node).second = value.second;
		return KL::pair<typename _base::iterator, bool>(_make_iterator(node), flag);
	}
	KL::pair<typename _base::iterator, bool> insert(key_type const &key)
	{
		bool flag;
		typename _base::_node_pointer node = _base::_insert(key, flag);
		return KL::pair<typename _base::iterator, bool>(_base::_make_iterator(node), flag);
	}
	// INSERT }
	// FIND {
	typename _base::iterator find(key_type const &key)
	{
		return _make_iterator(_base::_find(key));
	}
	// FIND }
	// ITERATOR {
	typename _base::iterator begin()
	{
		return (typename _base::iterator)this->_make_iterator(_base::_begin());
	}	
	typename _base::iterator end()
	{
		return (typename _base::iterator)_make_iterator(_base::_end());
	}	
	typename _base::const_iterator begin() const
	{
		return (typename _base::iterator)_make_iterator(_base::_begin());
	}	
	typename _base::const_iterator end() const
	{
		return (typename _base::iterator)_make_iterator(_base::_end());
	}
	typename _base::reverse_iterator rbegin()
	{
		return (typename _base::reverse_iterator)_make_iterator(_base::_begin());
	}	
	typename _base::reverse_iterator rend()
	{
		return (typename _base::reverse_iterator)_make_iterator(_base::_end());
	}	
	typename _base::const_reverse_iterator rbegin() const
	{
		return (typename _base::reverse_iterator)_make_iterator(_base::_begin());
	}	
	typename _base::const_reverse_iterator rend() const
	{
		return (typename _base::reverse_iterator)_make_iterator(_base::_end());
	}
	// ITERATOR }
};

KL_END

#endif // _XTREE_H_VERSION_KL__
